package uk.org.landeg.euler;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class PrimeGen {
	public static void main(String[] args) {
		
		long start = System.currentTimeMillis();
//		Map<Integer,Long> resutls = new TreeMap<Integer, Long>();
//		for (int n = 2; n < 5000 ; n++) {
//			resutls.put(n, totient(n));
//		}
		generate((long)1e5);
		System.out.println("Generated " + primes.size() + " primes");
		long prod;
		long p1,p2;
		long phi;
		int i1,i2;
		int min = primes.size() / 3;
		int max = min * 2;
		double minRatio = 10000;
		
		ArrayList<Long> plist = new ArrayList<Long>();
		plist.addAll(primes);
		for (i1 = min ; i1 < max ; i1++) {
			p1 =plist.get(i1);
			for (i2 = i1 + 1 ; i2 < max-1 ; i2++) {
				p2 = plist.get(i2);
				prod = p1 * p2;
				if (prod > 1e7) {
					break;
				}
				phi = prod - p1 - p2 + 1;
				if (isPermutation(prod, phi)) {
					System.out.println(p1 + "," + p2 + "," + prod + "," + phi);
					
				}
			}
		}
		
		long end = System.currentTimeMillis();
		System.out.println("time taken : " + (end - start) + "ms");
		System.out.println();
	}

	static TreeSet<Long> primes = new TreeSet<Long>();
	static final long MAX_PRIME_RANGE = 1000000;
	static int primeCount = 0;
	static long maxPrime = 0;

	public static TreeSet<Long> getPrimes () {
		return primes;
	}
	
	public static void generate (long max) {
		long trial = (maxPrime == 0) ? 3 : maxPrime + 2;
		boolean isprime;
		
		if (primes.size() == 0) {
			primes.add(2L);
		}
		long maxTrial ;
		do {
			isprime = true;
			maxTrial = (int)Math.sqrt(trial) + 1;
			for (Long testFactor : primes) {
				if (testFactor > maxTrial) {
					break;
				}
				if (trial % testFactor == 0) {
					isprime = false;
					break;
				}
			}
			if (isprime) {
				primes.add(trial);
				maxPrime = (trial > maxPrime) ? trial : maxPrime;
				primeCount++;
			}
			maxPrime = (trial > maxPrime) ? trial + 1: maxPrime;
		} while ((trial+=2) <= max);
	}
	
	public static Map<Long, Integer> primeFactorise (long n) {
		Map<Long, Integer> factors = new HashMap<Long, Integer>();
		int factorCount;
		do {
			for (Long trialFactor : primes) {
				factorCount = 0;
				while (n % trialFactor == 0) {
					n /= trialFactor;
					factorCount++;
				}
				if (factorCount > 0) {
					factors.put(trialFactor, factorCount);
				} 
			}
		} while (n > 1);
		return factors;
	}
	
	public static Set<Long> primeFactors (long n) {
		Set<Long> factors = new TreeSet<Long>();
		do {
			for (Long trialFactor : primes) {
				while (n % trialFactor == 0) {
					n /= trialFactor;
					factors.add(trialFactor);
				}
			}
		} while (n > 1);
		return factors;
	}
	
	public static Set<Long> factorise (long n) {
		return factorise(n, true);
	}
	
	public static Set<Long> factorise (long n, boolean proper) {
		Set<Long> factors = new TreeSet<Long>();
		long max = (long)Math.sqrt(n) + 1;
		
		final boolean even = (n % 2 == 0);
		final int inc = (even) ? 2 : 1;
		long trial = 1;
		if (proper || even) {
			trial++;
		}
		do {
			if (n % trial == 0) {
				factors.add(trial);
				factors.add(n/trial);
			}
		} while ((trial += inc) <= max);
		return factors;
	}
	
	public static long lcm (long i, long n) {
		long max = Math.max(n, i);
		long min = Math.min(n, i); 
		generate (max);
		long maxCheck = (long)Math.sqrt(min) + 1;
		for (Long prime : primes) {
			if (prime > maxCheck) {
				break;
			} else {
				if (i % prime == 0 && n % prime == 0) {
					return prime;
				}
			}
		}
		return 1;
	}
	
	/** 
	 * returns the number of integers N(2..n-1) coprime to n.
	 * 
	 * @param n
	 * @return
	 */
	public static long totient (long n) {
		Set<Long> candidates = new TreeSet<Long> ();
		for (long j = 1; j < n ; j++) {
			candidates.add(j);
		}
		long max = (n / 2);
		generate (max);
		long prod,mult;
		for (long test : primes) {
			if (test > max ) {
				break;
			}
			if (n % test == 0) {
				mult = 1;
				do {
					prod = test * mult;
					candidates.remove(prod);
					if (prod >= n) {
						break;
					}
					mult++;
				} while (true);
			}
		}
		return candidates.size();
	}
	
	public static boolean isCoprime (long n, long i) {
		final long max = Math.max(n, i);
		final long min = Math.min(n, i);
		generate (max + 1);
		for (Long p : primes) {
			if (p > min) {
				break;
			}
			if (n%p==0 && i%p==0) {
				return false;
			}
		}
		return true;
	}
	
	public static boolean isPrimeFast (long n, int precis) {
		if (n <= maxPrime) {
			return isPrime(n);
		} else {
			return BigInteger.valueOf(n).isProbablePrime(precis);
		}
	}
	public static boolean isPrime (long n) {
		if (n <= maxPrime) {
			return primes.contains(n);
		} else if (n >= maxPrime * maxPrime && n <= MAX_PRIME_RANGE * MAX_PRIME_RANGE) {
			final long generateTo = (long)(Math.sqrt(n+ 1) );
			if (maxPrime < generateTo) {
				System.out.println("Generating primes up to " + generateTo);
				generate(generateTo);
			}
	
		} else if (n >= MAX_PRIME_RANGE * MAX_PRIME_RANGE){
			throw new RuntimeException();
		}
		for (long p : primes) {
			if (p >= n) {
				break;
			}
			if (n % p == 0) {
				return false;
			}
		}
		return true;
	}
	
	public static int[] getDigits (long n) {
		long start = n;
		try {
			int rtn[] = new int[10];
			do {
				rtn[(int)n%10]++;
				n/=10;
			} while (n > 0);
			return rtn;
		}catch (Exception e) {
			System.out.println("Something went wrong with " + start);
			System.exit(1);
			return null;
		}
	}
	
	public static boolean isPermutation (long n, long m) {
		return Arrays.equals(getDigits(n), getDigits(m));
	}
	
	public static long getMaxPrime() {
		return maxPrime;
	}
	
	
}
